package main.Q1601_1700;

public class Q1641_1650 {
	public static void main(String[] args) {
		System.out.println("Question1641：统计字典序元音字符串的数目");
		System.out.println("Question1642：");
		System.out.println("Question1643：");
		System.out.println("Question1644：");
		System.out.println("Question1645：");
		System.out.println("Question1646：获取生成数组中的最大值");
		System.out.println("Question1647：");
		System.out.println("Question1648：销售价值减少的颜色球");
		System.out.println("Question1649：");
		System.out.println("Question1650：");
	}
}

class Question1641 {
	public int countVowelStrings(int n) {
		int[] dp = {1, 1, 1, 1, 1};
		for (int i = 2; i <= n; i++) {
			for (int j = 0; j < 5; j++) {
				for (int k = j + 1; k < 5; k++) {
					dp[j] += dp[k];
				}
			}
		}
		int total = 0;
		for (int count : dp) total += count;
		return total;
	}
}

class Question1646 {
	public int getMaximumGenerated(int n) {
		int max = 0;
		if (n <= 1) max = n;
		else {
			int[] result = new int[n + 1];
			result[1] = 1;
			max = 1;
			for (int i = 1; i <= n; i++) {
				max = Math.max(max, result[i]);
				if (2 * i <= n) {
					result[2 * i] = result[i];
				}
				if (2 * i + 1 <= n) {
					result[2 * i + 1] = result[i] + result[i + 1];
				}
			}
		}
		return max;
	}
}

class Question1648 {
	public int maxProfit(int[] inventory, int orders) {
		int max = 0;
		final int MOD = (int) 1e9 + 7;
		for (int x : inventory) {
			max = Math.max(max, x);
		}
		int l = -1, r = max + 1;
		while (l + 1 < r) {
			int c = l + (r - l) / 2;
			if (check(inventory, orders, c)) {
				l = c;
			} else {
				r = c;
			}
		}
		long ans = 0;
		for (int x : inventory) {
			if (x > r) {
				ans += (x + r + 1) * 1L * (x - r) / 2;
				ans %= MOD;
				orders -= x - r;
			}
		}
		ans += r * 1L * orders;
		return (int) (ans % MOD);
	}

	public boolean check(int[] nums, int orders, int x) {
		int sum = 0;
		for (int num : nums) {
			sum += Math.max(num - x, 0);
			if (sum > orders) {
				return true;
			}
		}
		return false;
	}
}